//1.位运算 --- 只出现一次的数字III
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //1.先将所有的数异或在一起, 得到只出现一次的两个数字的异或结果
        int ret = 0;
        for(auto x : nums) 
            ret ^= x;
        //2.找到ret的二进制中第一次出现1的位置
        int pos = 0;
        for(int i = 0; i < 32; i++) 
            if(((ret >> i) & 1) == 1) 
            {
                pos = i;
                break;
            }
        //3.根据pos位置为0/1, 将nums中的所有数划分为两组, 每一组各自异或, 得到最终两个数
        int r1 = 0, r2 = 0;
        for(auto x : nums)
        {
            if(((x >> pos) & 1) == 0) 
                r1 ^= x;
            else 
                r2 ^= x;
        }
        return {r1, r2};
    }
};



//2.位运算 --- 消失的两个数字
//思路:将原数组和[1, n+2]数组放到一起, 转化成只出现一次的数字III
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0, n = nums.size();
        for(auto x : nums) ret ^= x;
        for(int i = 1; i <= n + 2; i++) ret ^= i;

        int pos = 0;
        for(int i = 0; i < 32; i++) 
            if(((ret >> i) & 1) == 1)
            {
                pos = i;
                break; 
            }
        
        int r1 = 0, r2 = 0;
        for(auto x : nums)
        {
            if(((x >> pos) & 1) == 1)
                r1 ^= x;
            else    
                r2 ^= x;
        }
        for(int i = 1; i <= n + 2; i++)
        {
            if(((i >> pos) & 1) == 1)
                r1 ^= i;
            else    
                r2 ^= i;
        }
        return {r1, r2};
    }
};


